package leetcode100;

import java.util.LinkedList;

public class lc023 {
    public static void main(String[] args) {
        Tree tree1 = new Tree();
        TreeNode root1 = tree1.root;
        tree1.visit();

        Tree tree2 = new Tree();
        TreeNode root2 = tree2.root;
        tree2.visit();
        lc023 lc = new lc023();
        TreeNode root3 = lc.mergeTrees(root1, root2);
        Tree tree3 = new Tree(root3);
        tree3.visit();

    }

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        LinkedList<TreeNode> queue1 = new LinkedList<>();
        LinkedList<TreeNode> queue2 = new LinkedList<>();
        LinkedList<TreeNode> queue3 = new LinkedList<>();

        TreeNode node1 = null;
        TreeNode node2 = null;
        TreeNode node3 = null;
        TreeNode root3 = null;

        /**
         * 获取root3根节点
         *
         */
        if (root1 == null && root2 != null) {
            root3 = new TreeNode(root2.val);
        } else if (root1 != null && root2 == null) {
            root3 = new TreeNode(root1.val);
        } else if (root1 != null && root2 != null) {
            root3 = new TreeNode(root1.val + root2.val);
        } else {
            return null;
        }

        queue1.add(root1);
        queue2.add(root2);
        queue3.add(root3);
        TreeNode left1 = null;
        TreeNode right1 = null;
        TreeNode left2 = null;
        TreeNode right2 = null;

        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            node1 = queue1.poll();
            node2 = queue2.poll();
            node3 = queue3.poll();

            if (node3 == null) {
                continue;
            }


            left1 = node1 == null ? null : node1.left;
            right1 = node1 == null ? null : node1.right;
            left2 = node2 == null ? null : node2.left;
            right2 = node2 == null ? null : node2.right;

            if (left1 == null && left2 == null) {
                node3.left = null;
            } else if (left1 != null && left2 == null) {
                node3.left = new TreeNode(left1.val);
            } else if (left2 != null && left1 == null) {
                node3.left = new TreeNode(left2.val);
            } else {
                node3.left = new TreeNode(left1.val + left2.val);
            }
            queue1.add(left1);
            queue2.add(left2);
            queue3.add(node3.left);

            if (right1 == null && right2 == null) {
                node3.right = null;
            } else if (right1 != null && right2 == null) {
                node3.right = new TreeNode(right1.val);
            } else if (right2 != null && right1 == null) {
                node3.right = new TreeNode(right2.val);
            } else {
                node3.right = new TreeNode(right1.val + right2.val);
            }

            queue1.add(left1);
            queue1.add(right1);
            queue2.add(left2);
            queue2.add(right2);
            queue3.add(node3.left);
            queue3.add(node3.right);
        }
        return root3;
    }

}

